/**
 * 递归，是很常见也很重要的一种程序设计思想
 *      定义：程序或者函数直接或间接的调用自己，称为递归
 *      思想：把大问题分解成小问题
 *      要素：
 *          1：递归的边界条件（用于确定何时终止递归）
 *          2：递归模式（如何把大问题分解成小问题的，也称递归体）
 *      应用举例：
 *          数的阶乘，斐波那契额数列，回文字（以下分别采用递归算法和非递归算法实现这三个问题）
 */


 // 数的阶乘

 /**
  * 阶乘描述：
  *     输入 n
  *     n = 0 , 返回 1
  *     n >= 1, 返回 n(n-1)!
  */
 function fact_recursion (n) {
    if (n == 0) { 
        return 1
    } else {
        return n*fact_recursion(n - 1)
    }
 }


 function fact__noRe (n) {
     let res = n
     while(--n >= 1) {
        res *= n
     }
     return res
 }


 /**
  * 斐波那契数列
  */
 function feibonaqie(n) {
    if (n <= 1) {
        return n
    } else {
        return feibonaqie(n - 1) + feibonaqie(n - 2)
    }
 }

 function feibonaqie_no(n) {
    let pre = 0,now = 1,next
    for(let j = 2; j <= n; j++) {
        next = pre + now
        pre = now
        now = next
    }
    return next
 }


 /**
  * 回文字判断
  */
 function palindrome(s, l, r) {
    if (l >= r) { 
        return 1
    } 
    if (s[l] === s[r]) {
        l = l + 1
        r = r - 1
        return palindrome(s, l++, r--)
    } else {
        return 0
    }
 }


 function palindrome_no(s, l, r) {
    while (l <= r) {
        if (s[l] !== s[r]) {
            return 0
        } 
        l++
        r--
    }
    return 1
 }

 console.log(palindrome_no(['n','o','o','n'], 0, 3));
 